package com.majia.map;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 马甲 on 2017/7/12/012.
 */
public class MyHashMap<K, V> implements MyMap<K, V> {

    //定义默认数组大小 16
    private static int defaultlenth = 1 << 4;

    //扩容标准 所使用的 usesize /数组长度 > 0.75
    //defaultAddSizeFactor过大 造成扩容概率变低 储存小 但是就是存取效率降低
    //0.9 有限的数组长度空间位置内会形成链表 存在或者取值都需要进行大量的遍历和判断(逻辑)
    private static double defaultAddSizeFactor = 0.75;

    //使用数组位置的总数
    private int useSize;
    //定义一个数组
    private Entry<K, V>[] table = null;

    public  MyHashMap(){
        this(defaultlenth, defaultAddSizeFactor);
    }
    public  MyHashMap(int length, double defaultAddSizeFactor){
        if(length < 0){
            throw new IllegalArgumentException("数组长度参数不能为负数,当前是"+length);
        }
        if(defaultAddSizeFactor <= 0 || Double.isNaN(defaultAddSizeFactor)){
            throw new IllegalArgumentException("扩容标准必须大于0,当前是"+defaultAddSizeFactor);
        }
        this.defaultlenth = length;
        this.defaultAddSizeFactor = defaultAddSizeFactor;
        table = new Entry[defaultlenth];
    }

    @Override
    public V put(K k, V v) {
        if(useSize > defaultlenth * defaultAddSizeFactor){
            up2Size();
        }
        int index = getIndex(k, table.length);
        Entry<K,V> entry = table[index];
        if(entry == null){
            table[index] = new Entry(k, v, null);
            useSize++;
        } else{
            table[index] = new Entry(k, v, entry);
        }
        return table[index].getValue();
    }

    public int useSize(){
        return useSize;
    }

    //用来通过自身数组长度和key来确定储存位置
    private int getIndex(K k, int length) {
        int m = length -1;
        int index = hash(k.hashCode()) & m;
        return index >=0 ? index : -index;
    }

    private int hash(int hashCode){
        hashCode = hashCode^((hashCode >>> 20)^(hashCode >>> 12));
        return hashCode^((hashCode >>> 7)^(hashCode >>> 4));
    }

    private void up2Size() {
        Entry<K,V>[] newTable = new Entry[2*defaultlenth];
        //老数组里面是有非常多Entry对象 这个对象位置 散列存在 在此散列
        againHash(newTable);
    }

    private void againHash(Entry<K, V>[] newTable) {
        List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();
        for (int i = 0; i < table.length; i++){
            if(table[i] == null){
                continue;
            }
            foundEntryByNext(table[i], entryList);
        }
        if(entryList.size() > 0){
            useSize = 0;
            defaultlenth = 2*defaultlenth;
            table = newTable;
            for(Entry<K, V> entry : entryList){
                if(entry.next != null){
                    //形成链表关系取消
                    entry.next = null;
                }
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    private void foundEntryByNext(Entry<K, V> entry, List<Entry<K, V>> entryList) {
        if(entry != null && entry.next != null){
            entryList.add(entry);
            foundEntryByNext(entry.next, entryList);
        } else{
            entryList.add(entry);
        }
    }

    @Override
    public V get(K k) {
        int index = getIndex(k, table.length);
        if(table[index] == null){
            throw  new NullPointerException();
        }
        return findValueByEqualKey(k, table[index]);
    }

    private V findValueByEqualKey(K k, Entry<K, V> entry) {
        if(k == entry.getKey() || k.equals(entry.getKey())){
            return entry.getValue();
        } else if(entry.next != null){
            return findValueByEqualKey(k, entry.next);
        }
        return null;
    }

    public static int getDefaultlenth() {
        return defaultlenth;
    }

    public static void setDefaultlenth(int defaultlenth) {
        MyHashMap.defaultlenth = defaultlenth;
    }

    public static double getDefaultAddSizeFactor() {
        return defaultAddSizeFactor;
    }

    public static void setDefaultAddSizeFactor(double defaultAddSizeFactor) {
        MyHashMap.defaultAddSizeFactor = defaultAddSizeFactor;
    }

    public int getUseSize() {
        return useSize;
    }

    public void setUseSize(int useSize) {
        this.useSize = useSize;
    }

    public Entry<K, V>[] getTable() {
        return table;
    }

    public void setTable(Entry<K, V>[] table) {
        this.table = table;
    }

    class Entry<K,V> implements MyMap.Entry<K, V>{
        K k;
        V v;
        Entry<K, V> next;
        public Entry(K k, V v, Entry<K, V> next){
            this.k = k;
            this.v = v;
            this.next = next;
        }
        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }
}
